public class Test {


    /**
     * @param str 主串
     * @param sub 字串
     * @param pos 从主串的pos开始匹配的位置
     * @return 返回匹配成功开始的下标
     */
    public static int KMP(String str,String sub,int pos) {
        if(str == null || sub == null) return -1;
        int lenStr = str.length();
        int lenSub = sub.length();
        if(lenStr == 0 || lenSub == 0) return -1;
        if(pos < 0 || pos >= lenStr) return -1;

        int[] next = new int[lenSub];
        getNext(sub,next);//求next数组
        int i = pos;//遍历主串
        int j = 0;//遍历子串
        while(j < lenSub && i < lenStr) {
            //j==-1时，一开始就匹配失败了；j需要走回0位置，i得往下走
            if(j == -1 || str.charAt(i) == sub.charAt(j)) {
                i++;
                j++;
            }else {
                j = next[j];
            }
        }
        if(j >= lenSub) {
            return i-j;
        }
        return -1;
    }
    public static void getNext(String sub,int[] next) {
        if(sub.length() == 1) {
            next[0] = -1;
            return;
        } else if (sub.length() == 2) {
            next[0] = -1;
            next[1] = 0;
            return;
        }
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int k = 0;
        while(i < sub.length()) {
            if(k == -1 || sub.charAt(i-1) == sub.charAt(k)) {
                next[i] = k+1;
                k++;
                i++;
            }else {
                k = next[k];
            }
        }
    }
    public static void main(String[] args) {
        String str = "ababcabcd";//主串
        String sub = "abc";//字串
        int start = KMP(str,sub,0);
        if(start != -1) {
            System.out.println(str.substring(start,start+sub.length()));
        } else {
            System.out.println("找不到！");
        }
        System.out.println(KMP("ababcabcd","ab",0));//0
        System.out.println(KMP("ababcabcd","eee",0));//-1
        System.out.println(KMP("ababcabcd","abcd",0));//5
    }
    public static int BF(String str,String sub) {
        if(str == null || sub == null) {
            return -1;
        }
        int lenStr = str.length();
        int lenSub = sub.length();
        if(lenStr == 0 || lenSub == 0) {
            return -1;
        }
        int i = 0;
        int j = 0;
        while(j < lenSub && i < lenStr) {
            if(str.charAt(i) == sub.charAt(j)) {
                i++;
                j++;
            } else {
                i = i-j+1;
                j = 0;
            }
        }
        if(j >= lenSub) {
            return i-j;
        }
        return -1;
    }
    public static void main1(String[] args) {
        String str = "ababcabcd";//主串
        String sub = "abc";//字串
        int start = BF(str,sub);
        if(start != -1) {
            System.out.println(str.substring(start,start+sub.length()));
        } else {
            System.out.println("找不到！");
        }
    }
}
